package org.example.myleet.rosalind.fibd;

import java.math.BigInteger;

public class Solution {
    public BigInteger rabbitWithDying(int n, int m) {
        //Attention! The result may be very big and exceed long.
        //0-mature, 1-cub, 2-total
        BigInteger[][] dp = new BigInteger[n][2];
        //the first month, no mature, only one cub
        dp[0][0] = BigInteger.ZERO;
        dp[0][1] = BigInteger.ONE;
        for (int i = 1; i < n; ++i) {
            //the next month
            //cubs are produced by last month's matures
            dp[i][1] = dp[i - 1][0];
            //matures are from last month's matures and cubs grown up
            dp[i][0] = dp[i - 1][0].add(dp[i - 1][1]);
            //j is the m month before month i
            int j = i - m;
            if (j >= 0) {
                //if month j has cub, then these cubs die, reduced from matures
                dp[i][0] = dp[i][0].subtract(dp[j][1]);
            }
        }
        //total = mature + cub
        return dp[n - 1][0].add(dp[n - 1][1]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rabbitWithDying(6, 3));
        System.out.println(solution.rabbitWithDying(85, 17));
        System.out.println(solution.rabbitWithDying(92, 20));
    }
}
